CENG315 - Algorithms HW#3 (Due date: 27/10/2002)

Guess The Ball!

Guess the ball is a game played between two players. There are K (1 <= K <= 100) different kinds of balls (numbered with integers 1 through K, consecutively). N (1 <= N <= 1000) balls of various kinds are put in a box. Both players know exactly how many balls of each kind there are in the box. Your opponent randomly picks and removes a ball without letting you see it, and wants you to find out the kind of the ball. To find this you can ask the following question:

• Is it of the kind k₁ or k₂ or ... k_m? (where m <= K)

The answer of your question will be either “yes” or “no”. After you correctly identify the kind of the ball, your opponent picks another ball, and so on until all boxes become empty. Initial steps of a sample game is given below.

Suppose there are 5 kinds of balls and box initially contains 10 balls of kind 1, 8 balls of kind 2, 3 balls of kind 3, 7 balls of kind 4 and 4 balls of kind 5. Your opponent picks a ball of kind 4. A possible sequence of questions is: Is it of the kind 1 or 2 or 5? no Is it of the kind 3? no Ball is of kind 4 After the ball is correctly identified number of balls of kind 4 decrease to 6 and your opponent selects another ball.

Initial steps of a sample game.

Your objective in the game is to minimize the total number of questions you ask. In the next round, the roles are switched (you start picking balls and your opponent starts asking questions) and one who asked less number of questions wins. In this homework you will implement only one round of the game against computer where computer picks the balls and you (your program) ask questions. Interaction of your program with computer will be through two functions called ask_kind and tell. Function prototypes and description is as follows:

int ask_kind(int size, int *kind);

Is the ball picked of kind kind[0] or ... kind[size – 1]? Returns 1 if answer is “yes”, otherwise returns 0.

void tell(int k);

If the ball is of kind k function does nothing, otherwise your program terminates immediately.

Input

The first line of the input file balls.inp contains a single integer K denoting the number of the kinds of balls. Each of the following K lines contains the number of balls of the respective kind such that the (k+1)'th line of the input file contains the number of balls of kind k (1 <= k <= K)

nuts.inp:

5
10
8
3
7
4

Output

No output :) Your program must terminate normally after all balls are picked from the box.